-
Notifications
You must be signed in to change notification settings - Fork 0
/
Analizador.hs
284 lines (245 loc) · 10.6 KB
/
Analizador.hs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
-- Tema_12/Analizador.hs
-- Tema 12: Analizadores sintácticos funcionales
module Tema_12.Analizador where
import Data.Char ( isAlpha
, isAlphaNum
, isDigit
, isLower
, isSpace
, isUpper
)
-- ---------------------------------------------------------------------
-- § El tipo de los analizadores --
-- ---------------------------------------------------------------------
-- El tipo de los analizadores.
type Analizador a = String -> [(a,String)]
-- (analiza a cs) es el resultado de aplicar el analizador a a la
-- cadena cs.
analiza :: Analizador a -> String -> [(a,String)]
analiza a = a
-- ---------------------------------------------------------------------
-- § Analizadores básicos --
-- ---------------------------------------------------------------------
-- El analizador (resultado v) siempre tiene éxito, devuelve v y no
-- consume nada. Por ejemplo,
-- analiza (resultado 3) "Hola" == [(3,"Hola")]
resultado :: a -> Analizador a
resultado v = \ent -> [(v,ent)]
-- El analizador fallo siempre falla. Por ejemplo,
-- analiza fallo "Hola" == []
fallo :: Analizador a
fallo = \_ -> []
-- El analizador elemento falla si la cadena es vacía y consume el primer
-- elemento en caso contrario. Por ejemplo,
-- analiza elemento "Hola" == [('H',"ola")]
-- analiza elemento "" == []
elemento :: Analizador Char
elemento = \xs -> case xs of
[] -> []
(y:ys) -> [(y,ys)]
-- ---------------------------------------------------------------------
-- § Secuenciación --
-- ---------------------------------------------------------------------
-- ((p >*> f) e) falla si el análisis de e por p falla, en caso
-- contrario, se obtiene un valor (v) y una salida (s), se aplica la
-- función f al valor v obteniéndose un nuevo analizador con el que se
-- analiza la salida s.
infixr 5 >*>
(>*>) :: Analizador a -> (a -> Analizador b) -> Analizador b
p >*> f = \ent -> case analiza p ent of
[] -> []
[(v,sal)] -> analiza (f v) sal
_ -> error "Imposible"
-- ---------------------------------------------------------------------
-- § Elección --
-- ---------------------------------------------------------------------
-- ((p +++ q) e) analiza e con p y si falla analiza e con q. Por
-- ejemplo,
-- analiza (elemento +++ resultado 'd') "abc" == [('a',"bc")]
-- analiza (fallo +++ resultado 'd') "abc" == [('d',"abc")]
-- analiza (fallo +++ fallo) "abc" == []
(+++) :: Analizador a -> Analizador a -> Analizador a
p +++ q = \ent -> case analiza p ent of
[] -> analiza q ent
[(v,sal)] -> [(v,sal)]
_ -> error "Imposible"
-- ---------------------------------------------------------------------
-- Primitivas derivadas --
-- ---------------------------------------------------------------------
-- (sat p) es el analizador que consume un elemento si dicho elemento
-- cumple la propiedad p y falla en caso contrario. Por ejemplo,
-- analiza (sat isLower) "hola" == [('h',"ola")]
-- analiza (sat isLower) "Hola" == []
sat :: (Char -> Bool) -> Analizador Char
sat p = elemento >*> \x ->
if p x then resultado x else fallo
-- digito analiza si el primer carácter es un dígito. Por ejemplo,
-- analiza digito "123" == [('1',"23")]
-- analiza digito "uno" == []
digito :: Analizador Char
digito = sat isDigit
-- minuscula analiza si el primer carácter es una letra
-- minúscula. Por ejemplo,
-- analiza minuscula "eva" == [('e',"va")]
-- analiza minuscula "Eva" == []
minuscula :: Analizador Char
minuscula = sat isLower
-- mayuscula analiza si el primer carácter es una letra
-- mayúscula. Por ejemplo,
-- analiza mayuscula "Eva" == [('E',"va")]
-- analiza mayuscula "eva" == []
mayuscula :: Analizador Char
mayuscula = sat isUpper
-- letra analiza si el primer carácter es una letra. Por ejemplo,
-- analiza letra "Eva" == [('E',"va")]
-- analiza letra "eva" == [('e',"va")]
-- analiza letra "123" == []
letra :: Analizador Char
letra = sat isAlpha
-- alfanumerico analiza si el primer carácter es una letra o un
-- número. Por ejemplo,
-- analiza alfanumerico "Eva" == [('E',"va")]
-- analiza alfanumerico "eva" == [('e',"va")]
-- analiza alfanumerico "123" == [('1',"23")]
-- analiza alfanumerico " 123" == []
alfanumerico :: Analizador Char
alfanumerico = sat isAlphaNum
-- (caracter x) analiza si el primer carácter es igual al carácter
-- x. Por ejemplo,
-- analiza (caracter 'E') "Eva" == [('E',"va")]
-- analiza (caracter 'E') "eva" == []
caracter :: Char -> Analizador Char
caracter x = sat (== x)
-- (cadena c) analiza si empieza con la cadena c. Por ejemplo,
-- analiza (cadena "abc") "abcdef" == [("abc","def")]
-- analiza (cadena "abc") "abdcef" == []
cadena :: String -> Analizador String
cadena [] = resultado []
cadena (x:xs) = caracter x >*> \y ->
cadena xs >*> \ys ->
resultado (y:ys)
-- (varios p) aplica el analizador p cero o más veces. Por ejemplo,
-- analiza (varios digito) "235abc" == [("235","abc")]
-- analiza (varios digito) "abc235" == [("","abc235")]
varios :: Analizador a -> Analizador [a]
varios p = varios1 p +++ resultado []
-- (varios1 p) aplica el analizador p una o más veces. Por ejemplo,
-- analiza (varios1 digito) "235abc" == [("235","abc")]
-- analiza (varios1 digito) "abc235" == []
varios1 :: Analizador a -> Analizador [a]
varios1 p = p >*> \v ->
varios p >*> \vs ->
resultado (v:vs)
-- ident analiza si comienza con un identificador (i.e. una cadena que
-- comienza con una letra minúscula seguida por caracteres
-- alfanuméricos). Por ejemplo,
-- analiza ident "lunes12 de Ene" == [("lunes12"," de Ene")]
-- analiza ident "Lunes12 de Ene" == []
ident :: Analizador String
ident = minuscula >*> \x ->
varios alfanumerico >*> \xs ->
resultado (x:xs)
-- nat analiza si comienza con un número natural. Por ejemplo,
-- analiza nat "14DeAbril" == [(14,"DeAbril")]
-- analiza nat " 14DeAbril" == []
nat :: Analizador Int
nat = varios1 digito >*> \xs ->
resultado (read xs)
-- espacio analiza si comienza con espacios en blanco. Por ejemplo,
-- analiza espacio " a b c" == [((),"a b c")]
espacio :: Analizador ()
espacio = varios (sat isSpace) >*> \_ ->
resultado ()
-- ---------------------------------------------------------------------
-- § Tratamiento de espacios --
-- ---------------------------------------------------------------------
-- (unidad p) ignora los espacios en blanco y aplica el analizador
-- p. Por ejemplo,
-- analiza (unidad nat) " 14DeAbril" == [(14,"DeAbril")]
-- analiza (unidad nat) " 14 DeAbril" == [(14,"DeAbril")]
unidad :: Analizador a -> Analizador a
unidad p = espacio >*> \_ ->
p >*> \v ->
espacio >*> \_ ->
resultado v
-- identificador analiza un identificador ignorando los espacios
-- delante y detrás. Por ejemplo,
-- analiza identificador " lunes12 de Ene" == [("lunes12","de Ene")]
identificador :: Analizador String
identificador = unidad ident
-- natural analiza un número natural ignorando los espacios delante
-- y detrás. Por ejemplo,
-- analiza natural " 14DeAbril" == [(14,"DeAbril")]
natural :: Analizador Int
natural = unidad nat
-- (simbolo xs) analiza la cadena `xs` ignorando los espacios delante
-- y detrás. Por ejemplo,
-- analiza (simbolo "abc") " abcdef" == [("abc","def")]
simbolo :: String -> Analizador String
simbolo xs = unidad (cadena xs)
-- listaNat analiza una lista de naturales ignorando los
-- espacios. Por ejemplo,
-- analiza listaNat " [ 2, 3, 5 ]" == [([2,3,5],"")]
-- analiza listaNat " [ 2, 3,]" == []
listaNat :: Analizador [Int]
listaNat = simbolo "[" >*> \_ ->
natural >*> \n ->
varios (simbolo "," >*> \_ ->
natural) >*> \ns ->
simbolo "]" >*> \_ ->
resultado (n:ns)
-- ---------------------------------------------------------------------
-- § Expresiones aritméticas --
-- ---------------------------------------------------------------------
-- expr analiza una expresión aritmética devolviendo su valor. Por
-- ejemplo,
-- analiza expr "2*3+5" == [(11,"")]
-- analiza expr "2*(3+5)" == [(16,"")]
-- analiza expr "2+3*5" == [(17,"")]
-- analiza expr "2*3+5abc" == [(11,"abc")]
expr :: Analizador Int
expr = term >*> \t ->
(simbolo "+" >*> \_ ->
expr >*> \e ->
resultado (t+e))
+++ (simbolo "-" >*> \_ ->
expr >*> \e ->
resultado (t-e))
+++ resultado t
-- term analiza un término de una expresión aritmética devolviendo su
-- valor. Por ejemplo,
-- analiza term "2*3+5" == [(6,"+5")]
term :: Analizador Int
term = factor >*> \f ->
(simbolo "*" >*> \_ ->
term >*> \t ->
resultado (f*t))
+++ (simbolo "/" >*> \_ ->
term >*> \t ->
resultado (f `div` t))
+++ resultado f
-- factor analiza un factor de una expresión aritmética devolviendo su
-- valor. Por ejemplo,
-- analiza factor "2*3+5" == [(2,"*3+5")]
-- analiza factor "(2+3)*5" == [(5,"*5")]
-- analiza factor "(2+3*7)*5" == [(23,"*5")]
factor :: Analizador Int
factor = (simbolo "(" >*> \_ ->
expr >*> \e ->
simbolo ")" >*> \_ ->
resultado e)
+++ natural
-- (valor cs) analiza la cadena cs devolviendo su valor si es una
-- expresión aritmética y un mensaje de error en caso contrario. Por
-- ejemplo,
-- valor "2*3+5" == 11
-- valor "2*(3+5)" == 16
-- valor "2 * 3 + 5" == 11
-- valor "2*3x+5y" == *** Exception: entrada sin usar x+5y
-- valor "-1" == *** Exception: entrada no valida
valor :: String -> Int
valor xs = case (analiza expr xs) of
[(n,[])] -> n
[(_,sal)] -> error ("entrada sin usar " ++ sal)
[] -> error "entrada no valida"
_ -> error "Imposible"